"""
Copyright (c) 2007 Daniel Garcia Moreno <danigm@gmail.com>
Copyright (c) 2007 Eduardo Robles Elvira <edulix@gmail.com>
Licence: GPLv2
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
"""
from Graph import *
from Vertex import *
from copy import *
import pdb
import time


def Dijkstra(graph, start_vertex, end_vertex = None):
	"""
	Arguments:
	@graph to use in the algorithm
	@start_vertex the begining of the path, the name
	@end_vertex the end of the path, the name
		
	How does it work?
	I have a list of vertices, and for each vertex it contains a list formed with the vertex
	in question, its tag (distance to start_vertex), and its father. So in essence, vertices
	has this form: [[vertex, tag(number), father(vertex)],...]
	
	When the algorithm finishes, vertices contains the list of vertices with the distance to
	the start_vertex, and with their fathers, and then I can make the path from the end vertex
	to the start, following the fathers hierarchy.
	
	See http://en.wikipedia.org/wiki/Dijkstra's_algorithm for more information about the algorithm
				
	Variables:
	@vertices [[vertex, tag(number), father(vertex)],...]
	@num_visited number of visited vertices. just for convenience. should be the same as len(visited)
	@visited list of visited vertices
	@active_vertex the active vertex
	"""
	queue = copy(graph.get_vertices())
	vertices = []
	for v in queue:
		vertices.append([v, float('inf'), None]) #[vertex, tag, father]
	
	active_vertex = graph.find_by_name(start_vertex)

	i = index(vertices, active_vertex)
	vertices[i] = [active_vertex, 0, None] #the first vertex don't have father, and the distance is 0
	
	while len(queue) >= 0:
		u = extract_min(queue, vertices)
		if u == None:
			break
		i_u = index(vertices, u)
		for adj in u.get_adjacents():
			i_adj = index(vertices, adj)
			w = graph.get_weight(u.get_name(), adj.get_name())
			if vertices[i_u][1] + w < vertices[i_adj][1]:
				vertices[i_adj][1] = vertices[i_u][1] + w
				vertices[i_adj][2] = u
            
	if end_vertex == None:
		return graph, vertices
	else:
		return calc_path(graph.find_by_name(end_vertex), vertices)


def extract_min(queue, vertices):
	"""
	 u := Extract_Min(Q, vertices) searches for the vertex u in the vertex set Q that has the least tag value. That vertex is removed from the set Q and returned to the user.
	"""
	min_tag_value = float('inf')
	ret = None
	for v in queue:
		i = index(vertices, v) # index of V in vertices
		if vertices[i][1] < min_tag_value:
			ret = v
			min_tag_value = vertices[i][1]
	
	if ret != None:
		queue.remove(ret)
	
	return ret	

def member(visited, vertex):
	"""
	return true if the vertex is member of the visited list
	"""
	for i in visited:
		if i == vertex:
			return True
	return False

def calc_path(end_vertex, vertices):
	"""
	calculates the dijkstra path recieving a list of vertices like this:
	vertices = [[vertex,tag,father], ...], and returns [weight_of_complete_path, start_vertex, ..., end_vertex]
	"""
	path = []
	i = vertices[index(vertices, end_vertex)]
	i_end = i
	path.append(i[0]) #the end_vertex
	while(i[2] != None): #the start_vertex doesn't have father
		path.append(i[2])
		i = vertices[index(vertices,i[2])] #we go to the father, and try again
	path.append(i_end[1]) #the weight
	path.reverse()
	return path

def index(v, a):
	"""
	return the index of a vertex in the list of (vertex,tag,father)
	locating this by the first component, the vertex.
	"""
	for i in v: #v is the list of vertices [[vertex, tag, father]], we only look for the vertex
		if a == i[0]:
			return v.index(i)
	return -1

def print_path(path):
	"""
	reicieve a list of vertex, and print its names
	"""
	print "length: " + str(path[0])
	path1 = path[1:]
	for i in path1:
		print i.get_name()

"""
Resources:
 * http://www.answers.com/topic/route-inspection-problem
   Contains a small and good explanation of the problem and the solution. Principal paragraph:
	
	If the graph is not Eulerian, it must contain vertices of odd degree. By a result in graph
	theory, there must be an even number of these types of vertices. Note that we must revisit
	edges that come out of these vertices for the solution. We make the graph Eulerian by
	doubling the paths that connect these vertices in pairs. We choose the pairs such that
	the total distance covered of all paths that connect these vertices are as small as
	possible. Now the solution is an Eulerian path for this new graph.

 * http://people.bath.ac.uk/tjs20/introduction.htm
   Algorithm explained step by step, very educative!
   Take a look specially to http://people.bath.ac.uk/tjs20/oddnetdisc.htm

 * http://www.uclic.ucl.ac.uk/harold/cpp/
   Contains a simple Java implementation
"""
def CPP(graph, sv="0",file="55.graph"):
	"""
	Steps:
	1) List all odd vertices in the network. There will be an even number of these. DONE
	2) In order to make the network Eulerian, find all possible sets of pairings of odd
	vertices in order to make them of even degree so that no odd vertices are left in the
	network. DONE
	3) For each set of pairings, for each pairing, find the shortest route you need to travel to
	get from one vertex in the pairing to the other. Hence, add up the total distance you need
	to travel for each set of possible pairings. DONE
	4) Choose the pairing with the minimum total distance and repeat these edges in the network,
	i.e. makes the associated vertices have an even degree. Note: there may be many different
	routes that can be constructed, all of which take the same minimum distance. DONE
	"""

	t = time.time()
	aa = False
	odd_v = odd_vertices(graph)
	if(len(odd_v) > 0):
		print "step 1"
		sets = sets_of_pairings(odd_v)
		print "step 2"
		best_set = best_set_of_pairing(sets, graph, odd_v)
		print "step 3"
		graph = eulerize_graph(best_set, graph)
		print "step 4"
		aa = True
	
	path = eulerian_circuit(graph,graph.find_by_name(sv))
	
	graph.print_graph()
	if aa == True:
		graph.save_to_file(file)
	print "step 5"
	
	print "tiempo total: ", time.time() - t

	ret = [ i.get_name() for i in path ]
	return ret




def eulerian_circuit(G, start_vertex):
	"""
	The algorithm is too simple:
	1. you go over the next edge that is not visited and you will finish in start vertex.
	2. if the number of edges of the path is less than the edges of the graph, take a
		new vertex that have an edge that not is visited an start again.
	3. Next in the original path, substitute the vertex with the new subpath.
		And go to step 2
	"""
	G.print_graph()
	H = deepcopy(G) #a copy of the graph to remove edges, and know which ones has left
	v = H.find_by_name(start_vertex.get_name())
	path = [v] #list of vertices, the result of the algorithm
	n = 0 #the start vertex of the subcycle, index in path
	while len(H.get_edges()) > 0:
		found = False
		for i in range(n, len(path)):
			if len(path[i].get_adjacents()) > 0:
				n = i
				found = True
				break
		if not found:
			print "aqui no debe llegar"
			break

		subcycle = [path[n]]
		next = path[n].get_adjacents()[0]
		while  next != path[n]:
			subcycle.append(next)
			remove_edge(subcycle[-1], subcycle[-2], H)
			next = next.get_adjacents()[0]
		
		subcycle.append(next)
		remove_edge(subcycle[-1], subcycle[-2], H)

		path = path[0:n] + subcycle + path[n+1:]

	return path

def n_aristas(T, G, ui):
	# T.count(ui)*2 is the number of edges that contains the vertex ui in the path T
	# len(G.find_by_name(ui.get_name()).get_adjacents()) is the number of edges that contains  the vertex ui in the original graph G
	return T.count(ui)*2 < len(G.find_by_name(ui.get_name()).get_adjacents())

def remove_edge(v1, v2, graph):
	v1.remove_adjacent(v2)
	v2.remove_adjacent(v1)
	
	# We remove the edge only when necesary, because how multigraphs are implemented
	if(not v1.get_adjacents().__contains__(v2) and not v2.get_adjacents().__contains__(v1)):
		edges = graph.get_edges()
		edges.pop(v1.get_name(), v2.get_name())

def eulerize_graph(best_set_of_pairings, graph):
	"""
	Given a graph and a best set of pairing, we convert the graph in a eurlerian
	graph duplicating the edges in each path found in the set of pairings
	
	WARNING!
	How are edges duplicated?
	A new adjacent is added to both vertices of the edge. That's all!
	What about the weight? Well, in this special case of multigraph where there
	are only duplicated edges when we add them in this function and where the
	duplicated edges has the same weight, it's not problematic.
	
	
	See the format of best_set_of_pairings in the function best_set_of_pairings()
	"""
	
	best_set_of_pairings = best_set_of_pairings[1:]
	for calc_path in best_set_of_pairings:
		prev = calc_path[1]
		calc_path = calc_path[2:]
		for vertex in calc_path:
			prev.add_adjacent(vertex)
			vertex.add_adjacent(prev)
			prev = vertex
	
	return graph

def best_set_of_pairing(sets_of_pairings, graph, odd_vertices):
	"""
	Receives a set of pairings [ pairing1, pairing2, .... ] where a pairing is similar to
	[ [v1, v2], [v3, v4], ... ].
	
	For each pairing, for each pair, it calculates the path from one vertex of pair to the other
	one, and returns a pairing in which the sums of the distances of its pairs is minimal.
	
	Returns something like this: [ sum, calc_path, calc_path, ... ], 
	where "sum" is the sum of the distances of the pairs, "calc_path" is like 
	[weight_of_complete_path, start_vertex, ..., end_vertex] and "pairing" is as explained
	before
	"""
	best = [ float('inf') ]
	dic = {}
	
	if len(dic) == 0:
		for i in odd_vertices:
			g, v = Dijkstra(graph, i)
			for j in odd_vertices:
				if j != i:
					path = calc_path(g.find_by_name(j), v)
					dic[(i,j)] = path

	for set_of_pairing in sets_of_pairings:
		current = [ 0 ]
		for pair in set_of_pairing:
			dijkstra = dic[(pair[0], pair[1])]
			current.append(dijkstra)
			current[0] += dijkstra[0]
		
		if(current[0] < best[0]):
			best = current
	
	return best


def sets_of_pairings(odd_vertices):
	n = len(odd_vertices)
	m = n / 2 #numero de elementos por subconjunto
	pairs = [ (a,b) for a in odd_vertices for b in odd_vertices if a!=b and a < b ]
	subsets = []
	head = pairs[-1]
	while pairs[0] != head:
		#pdb.set_trace()
		p = recursiva(pairs, [], m)
		if len(p) == m:
			subsets.append(p)
		x = pairs[0]
		pairs = pairs[1:]
		pairs.append(x)

	subsets2 = []
	for i in range(len(subsets)):
		este_no = False
		for j in range(i+1, len(subsets)):
			t = False
			for q in subsets[i]:
				if not member(subsets[j],q):
					t = True
					break
			if not t:
				este_no = True
		if not este_no:
			subsets2.append(subsets[i])


	return subsets2


def recursiva(pairs, cogidos, quiero):
	este = []
	for i in pairs:
		este_no = False
		for j in cogidos:
			if i[0] == j[0] or i[1] == j[0] or i[0] == j[1] or i[1] == j[1]:
				este_no = True
		if not este_no:
			este.append(i)
	if este == []:
		return []

	if(quiero == 1):
		cogidos.append(este[0])
	else:
		cogidos.append(este[0])
		recursiva(pairs, cogidos, quiero-1)
		return cogidos





def odd_vertices(graph):
	"""
	Returns the list of vertices (by name) of odd degree
	"""
	odd_vertices = []
	vertices = graph.get_vertices()
	for i in vertices:
		if len(i.get_adjacents()) % 2 == 1:
			odd_vertices.append(i.get_name())
	return odd_vertices
